package 动态规划.另类的;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/5 16:57
 */
public class lc516最长回文子序列 {

    /*
     这也验证了 , 我的结论:
     如果是 子数组 或者子串, f(i, j) 表示的是 以 i 靠头, 以 j 结尾 (这个 是严格的 要求!)
     而子序列 f(i ,j ) 表示的 是  [i , j ]内 怎么怎么样
     */
    public int f(int i,int j,String s){
        if(i > j){
            return 0;
        }
        if(i == j){
            return 1;
        }
        int ans1 = 0 , ans2 = 0, ans3 = 0;
        if(s.charAt(i) == s.charAt(j)){
//            ans1 = i ==j ? 1 : f(i + 1,j - 1,s) + 2;
            ans1 = f(i + 1,j - 1,s) + 2;
        }else{
            ans2 = f(i + 1, j ,s);
            ans3 = f(i , j - 1 ,s);
        }
        return Math.max(ans1,Math.max(ans2,ans3));
    }

    // 直接 秒
    public int dp(String s){
        int len =  s.length();
        int dp[][] = new int[len][len];
        for(int i = len - 1; i >= 0;i--){
            dp[i][i] = 1;
            for(int j = i + 1;j < len;j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len - 1];
    }




    @Test
    public void test(){
        String s = "bbbab";
        System.out.println(f(0,s.length() - 1, s));
        System.out.println(dp(s));
    }

}
